{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Big O for Python Data Structures\n",
    "In this lecture we will go over the Big O of built-in data structures in Python: Lists and Dictionaries."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lists\n",
    "\n",
    "In Python lists act as dynamic arrays and support a number of common operations through methods called on them. The two most common operations performed on a list are indexing and assigning to an index position. These operations are both designed to be run in constant time, O(1).\n",
    "\n",
    "Let's imagine you wanted to test different methods to construct a list that is [0,1,2...10000]. Let go ahead and compare various methods, such as appending to the end of a list, concatenating a list, or using tools such as casting and list comprehension.\n",
    "\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def method1():\n",
    "    l = []\n",
    "    for n in xrange(10000):\n",
    "        l = l + [n]\n",
    "\n",
    "def method2():\n",
    "    l = []\n",
    "    for n in xrange(10000):\n",
    "        l.append(n)\n",
    "\n",
    "def method3():\n",
    "    l = [n for n in xrange(10000)]\n",
    "\n",
    "def method4():\n",
    "    l = range(10000) # Python 3: list(range(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now test these methods using the timeit magic function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 162 ms per loop\n",
      "1000 loops, best of 3: 820 µs per loop\n",
      "1000 loops, best of 3: 307 µs per loop\n",
      "10000 loops, best of 3: 77.7 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit method1()\n",
    "%timeit method2()\n",
    "%timeit method3()\n",
    "%timeit method4()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can clearly see that the most effective method is the built-in range() function in Python!\n",
    "\n",
    "It is important to keep these factors in mind when writing efficient code. More importantly begin thinking about how we are able to index with O(1). We will discuss this in more detail when we cover arrays general. For now, take a look at the table below for an overview of Big-O efficiencies."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Table of Big-O for common list operations\n",
    "\n",
    "** Please note, in order to see this table, you may need to download this .ipynb file and view it locally, sometimes GitHub or nbveiwer have trouble showing the HTML for it... **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table>\n",
    "    \n",
    "        <tr>\n",
    "            <th>Operation </th>\n",
    "            <th>Big-O Efficiency</th>\n",
    "        </tr>\n",
    "    \n",
    "\n",
    "    <tr>\n",
    "        <td>index []</td>\n",
    "        <td>O(1)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>index assignment</td>\n",
    "        <td>O(1)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>append</td>\n",
    "        <td>O(1)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>pop()</td>\n",
    "        <td>O(1)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>pop(i)</td>\n",
    "        <td>O(n)</td>\n",
    "    </tr>\n",
    "    <tr >\n",
    "        <td>insert(i,item)</td>\n",
    "        <td>O(n)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>del operator</td>\n",
    "        <td>O(n)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>iteration</td>\n",
    "        <td>O(n)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>contains (in)</td>\n",
    "        <td>O(n)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>get slice [x:y]</td>\n",
    "        <td>O(k)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>del slice</td>\n",
    "        <td>O(n)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>set slice</td>\n",
    "        <td>O(n+k)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>reverse</td>\n",
    "        <td>O(n)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>concatenate</td>\n",
    "        <td>O(k)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>sort</td>\n",
    "        <td>O(n log n)</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>multiply</td>\n",
    "        <td>O(nk)</td>\n",
    "    </tr>\n",
    "\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dictionaries\n",
    "\n",
    "Dictionaries in Python are an implementation of a hash table. They operate with keys and values, for example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d = {'k1':1,'k2':2}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d['k1']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Something that is pretty amazing is that getting and setting items in a dictionary are O(1)! Hash tables are designed with efficiency in mind, and we will explore them in much more detail later on in the course as one of the most important data structures to undestand. In the meantime, refer to the table below for Big-O efficiencies of common dictionary operations:\n",
    "\n",
    "<table border=\"1\">\n",
    "<thead valign=\"bottom\">\n",
    "<tr class=\"row-odd\"><th class=\"head\">Operation</th>\n",
    "<th class=\"head\">Big-O Efficiency</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody valign=\"top\">\n",
    "<tr class=\"row-even\"><td>copy</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>get item</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>set item</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>delete item</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-even\"><td>contains (in)</td>\n",
    "<td>O(1)</td>\n",
    "</tr>\n",
    "<tr class=\"row-odd\"><td>iteration</td>\n",
    "<td>O(n)</td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion\n",
    "\n",
    "By the end of this section you should have an understanding of how Big-O is used in Algorithm analysis and be able to work out the Big-O of an algorithm you've developed. Get ready, there's a quiz up next!"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
